#include<iostream>
using namespace std;



void print(int *arr,int n);


void swap(int *left, int *right)
{
    int temp = *left;
    *left = *right;
    *right = temp;
}

//@note 方法二，覆盖
//void insertSort(int *a, int len)
//{
//	for (int j=1; j<len; j++)
//	{
//		int key = a[j];
//		int i = j-1;
//		while (i>=0 && a[i]>key)
//		{
//			a[i+1] = a[i];
//			i--;
//		}
//		a[i+1] = key;
//	}
//}git
//
void insertSort(int *arr ,int n)
{
    for(int i=1;i<n;i++)
    {
         for(int j=i;j>0;j--)
         {
              if(arr[j] < arr[j-1])
                  swap(arr[j],arr[j-1]);
              else
                  break;
         }
//           int j=i;
//           while(j>0 && arr[j] < arr[j-1])
//           {     swap(arr[j],arr[j-1]);
//                 j--;
//
//           }
    };

}

void print(int *arr,int n)
{
    for(int i=0;i<n;i++)
        cout<< arr[i]<<' ' ;
    cout<< endl;

 }

int main()
{
    int a[11] ={2, 8, 4, 5, 9, 4, 42, 0, 3, 6, 8};
    int n=11;
    insertSort(a,n);
    print(a,n);
    return 0;
}


